Finite element analysis is a fundamental numerical analysis technique. The goal of finite element analysis is to solve a set of partial differential equations over a geometrical domain. A mesh corresponds to a discretization of the geometrical domain and includes a collection of mesh entities. The mesh entities often have simple shapes. For example, zero-dimensional mesh entities include vertices, one-dimensional mesh entities include lines, two-dimensional mesh entities include triangles or quandrangles, and three-dimensional mesh entities include tetrahedra, hexahedra or prisms.
Quadrilateral meshing often breaks a domain into a structured set of quadrilaterals, where interior nodes have four adjacent elements. Quadrilateral meshing has evolved in two major areas: local quadrilateral meshing and global quadrilateral meshing. FIG. 1(A) and FIG. 1(B) depict example diagrams showing local quadrilateral meshing and global quadrilateral meshing respectively. As shown in FIG. 1(A), local quadrilateral meshing uses a paving approach or a Q-Morph approach. For example, according to the paving approach (e.g., Ted D. Blacker, and Michael B. Stephenson, “Paving: A new approach to automated quadrilateral mesh generation,” International Journal for Numerical Methods in Engineering 32.4 (1991): 811-847), a row of quadrilateral elements is generated along an existing boundary, and another row of quadrilateral elements is generated inside of the boundary. The Q-Morph approach (e.g., Steven J. Owen, et al., “Q-Morph: an indirect approach to advancing front quad meshing,” International Journal for Numerical Methods in Engineering 44.9 (1999): 1317-1340) starts with a background mesh obtained by triangulation of a surface. An initial front is defined from one or more edges in the background mesh. An edge in the background mesh adjacent to only one triangle becomes part of the initial front. Each edge on the front is initially sorted according to a state of the edge which defines how the edge is to be used in forming a quadrilateral element. Angles between adjacent front edges determine the state of an individual front. For example, a minimum deviation energy is used for determining two new front edges.
Each front edge is individually processed to create a new quadrilateral element from the triangles in the background mesh. Particularly, a front edge is used as the initial base edge of a quadrilateral element, and one or more side edges are defined, e.g., by swapping the diagonal of adjacent triangles, or by splitting triangles to create a new edge. A top edge is generated between two nodes at the ends of two side edges by modifying the local triangulation using local edge swaps. The quadrilateral element is formed by merging any triangles bounded by the front edge, the side edges and the top edge and smoothed locally. The edges on the front that have two quadrilateral adjacencies are removed from the front, and edges that have one triangle and one quadrilateral adjacency are added to the front. Front edge processing continues until all edges on the front have been depleted.
As shown in FIG. 1(B), global quadrilateral meshing involves generation of a directional field that satisfies a set of directional constraints. Then, a globally smooth parameterization may be computed based on the directional field for mesh generation (e.g., David Bommes, Henrik Zimmer, and Leif Kobbelt, “Mixed-integer quadrangulation,” ACM Transactions on Graphics (TOG). Vol. 28. No. 3. ACM, 2009).